1. Field of the Invention
The present invention relates to detecting routing loops in a network and specifically to detecting routing loops in a network based on time-to-live (TTL) expiries.
2. Brief Description of the Related Art
Routing loops are inevitable in networks, such as Internet Protocol (IP) and Multi Protocol Label Switched (MPLS) networks. A routing loop occurs when a router incorrectly sends a data packet to a router through which the data packet already passed, thereby creating a circuitous path around which the data packet travels. Routing loops can be generally classified as transient or persistent. Transient routing loops last for a relatively short period of time (e.g., a few of seconds to a few minutes). Transient routing loops are typically caused by inconsistent routing among a set of routers that can occur subsequent to a network failure or configuration change. When the routing converges after such an event, these transient routing loops no longer exist.
Persistent routing loops in networks, such as IP and MPLS, can last for hours, days, or longer. These persistent routing loops are typically less common than transient routing loops, but tend to have a greater impact on network performance due to lost data traffic and wasted bandwidth. Persistent routing loops generally occur as a result of configuration errors, such as errors in a routing table, and hidden design vulnerabilities that are exposed only during failures. Due to the negative impacts of persistent routing loops, it is important for service providers to quickly detect and resolve these persistent routing loops. Relying on customer complaints to detect routing loops in a provider network is an undesirable approach.
Some conventional approaches to detecting routing loops can be classified as control plane and data plane methods. In control plane methods, routing tables from a set of routers are examined for routing inconsistencies and loops. These routing tables can include a large number of routes. For example, routing tables in “tier 1” Internet Service Provider (ISP) networks currently include about two hundred and fifty thousand routes. In large networks, routing changes can occur daily. As a result, validation of routing is required on a regular basis. This tends to be burdensome to service providers since large routing tables on many routers need to be examined for validation. Furthermore, such validation of routing does not guarantee loop-free routing. For example, while the control plane can be validated to ensure correct routing information, hardware or software malfunctions on a router could result in routing loops in the data plane.
Data plane methods for routing loop detection typically rely on sending probes to detect loops. For example, trace-route packets can be sent to validate loop-free routing. Such a method is generally only practical for small networks because even when a limited amount of probe traffic is sent from edge router to edge router, the number of edge router to edge router paths in medium to large networks is prohibitive. Another option is to send probes among a selected subset of edge routers. Although this would improve feasibility of this method, it does not ensure detection of routing loops associated with edge routers that are excluded from consideration.